/*
 * @lc app=leetcode.cn id=174 lang=cpp
 *
 * [174] 地下城游戏
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int calculateMinimumHP(vector<vector<int>> &dungeon)
    {

        const int M = dungeon.size();
        const int N = dungeon[0].size();

        vector<vector<int>> dp(M+1, vector<int>(N+1, 0));
        for(int i = 0; i < N+1; i++) dp[M][i] = INT_MAX;
        for(int i = 0; i < M+1; i++) dp[i][N] = INT_MAX;

        dp[M-1][N] = dp[M][N-1] = 1;

        //dp[i][j]表示从坐标i,j到达终点时所需的最小初始值
        for(int r = M-1; r >= 0; r--)
        {
            for(int c = N-1; c >= 0; c--)
            {
                dp[r][c] = max(min(dp[r+1][c], dp[r][c+1]) - dungeon[r][c], 1);
            }
        }

        return dp[0][0];
    }
};

// int main()
// {
//     // vector<vector<int>> v = {{0}};
//     vector<vector<int>> v = {{1, -3, 3}, {0, -2, 0}, {-3,-3,-3}};

//     cout << Solution().calculateMinimumHP(v) << endl;
//     return 0;
// }

// @lc code=end
